/*
 * @lc app=leetcode.cn id=386 lang=java
 *
 * [386] 字典序排数
 */

// @lc code=start

import java.util.List;
import java.util.ArrayList;

class Solution {
    List<Integer> res = new ArrayList<>();
    public List<Integer> lexicalOrder(int n) {
        for(int i = 1; i <= 9; i++) {
            dfs(i, n);
        }
        return res;
    }

    private void dfs(int cur, int n) {
        if(cur > n) {
            return;
        }

        res.add(cur);

        for(int i = 0; i <= 9; i++) {
            dfs(cur * 10 + i, n);
        }
    }
}
// @lc code=end

